训练指南 UVA - 11090（最短路BellmanFord+ 二分判负环）

Diposting di | Edited on

Going in Cycle!!

UVA - 11090

题意

就最小的环的平均权值

题解

分枚举平均值mid，只需判断是否存在平均值小于mid的回路，即判断是否有sum(wi)<mid*k （1≤i≤k），只需判断是否有sum(wi-mid)<0，只需将边权值减去mid后，判断是否存在负环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+10;
const int inf=1000000000;
struct Edge
{
    int from, to;
    double dist;
    Edge() {}
    Edge(int u, int v, double d) : from(u), to(v), dist(d) {}
};
struct BellmanFord{
    int n,m;
    vector<Edge>edges;
    vector<int> G[maxn];
    bool inq[maxn]; /// 是否在队列中
    double d[maxn];    /// s到各个点的距离  double 要改成double类型
    int p[maxn];    /// 最短路中的上一条弧
    int cnt[maxn];  /// 进队次数
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int dist)
    {
        edges.emplace_back(from, to, dist);
        m = edges.size();
        G[from].push_back(m - 1);
    }
    bool bellmanford(int s){
        queue<int>Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } //如果只判负环用这个
        /*for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;inq[s]=true;Q.push(s);*/
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=false;
            for(auto& id:G[u]){
                Edge& e=edges[id];
                if(d[u]<inf && d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u] + e.dist;
                    p[e.to]=id;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=true;
                        if(++cnt[e.to]>n)return true;
                    }
                }
            }
        }
        return false;
    }
};
BellmanFord solver;
bool test(double x){
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist-=x;
    bool ret=solver.bellmanford(0);
    for(int i=0;i<solver.m;i++)
        solver.edges[i].dist+=x;
    return ret;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++){
        int n,m;
        scanf("%d%d",&n,&m);
        solver.init(n);
        int ub=0;
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);u--;v--;ub=max(ub,w);
            solver.AddEdge(u,v,w);
        }
        printf("Case #%d: ", kase);
        if(!test(ub+1))printf("No cycle found.\n");
        else{
            double l=0,r=ub;
            while(r-l>1e-4){
                double mid=l+(r-l)/2;
                if(test(mid))r=mid;
                else l=mid;
            }
            printf("%.2f\n",l);
        }
    }
    return 0;
}